package com.zpself.module.算法练习.链表;

import java.util.Stack;
/**
*  给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 *
* @author  ZengPeng
* @date  2021/2/5
**/
class 力扣_2_两数相加 {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(2);
        ListNode n2 = new ListNode(4);
        ListNode n3 = new ListNode(3);
        n1.next=n2;
        n2.next=n3;

        ListNode t1 = new ListNode(5);
        ListNode t2 = new ListNode(6);
        ListNode t3 = new ListNode(4);
        t1.next=t2;
        t2.next=t3;
        //栈
        //  System.out.println(new 两数相加().addTwoNumbers(n1,t1));
         System.out.println(new 力扣_2_两数相加().addTwoNumbers2(n1,t1));
    }


    //直接生成结果
    private ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode result = new ListNode();//创建返回值
        ListNode p = result;//最下面的那个节点
        int isUp = 0;//是否进位
        int n1=0, n2=0,n3;
        while (l1!=null || l2!=null ||isUp!=0){
            if(l1!=null){n1 = l1.val;l1= l1.next;}
            if(l2!=null){n2 = l2.val;l2= l2.next;}
            n3 =isUp+n1+n2;
            isUp = n3>=10? 1:0;
            p.next = new ListNode(n3%10);p =p.next ;
            n1=0;n2=0;
        }
        return result.next;
    }


    //用栈
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //遍历压栈
        Stack<Integer> stack1 =new Stack<>();
        while (l1!=null){
            stack1.push(l1.val);
            l1=l1.next;
        }
        Stack<Integer> stack2 =new Stack<>();
        while (l2!=null){
            stack2.push(l2.val);
            l2=l2.next;
        }
        //弹栈求和
        Stack<Integer> stack3 =new Stack<>();
        boolean isUp = false;
        int n1=0, n2=0,n3;
        while (!stack1.empty() || !stack2.empty()){
            if (!stack1.empty())
                n1 = stack1.pop();
            if (!stack2.empty())
                n2 = stack2.pop();
            n3 =isUp? 1+n1+n2 : n1+n2;
            isUp = n3>=10;
            stack3.push(n3%10);
            System.out.println(n3%10);
            n1=0;n2=0;
        }
        if(isUp)
            stack3.push(1);

        //创建返回值
        ListNode result =new ListNode();
        ListNode p =null;
        while (!stack3.empty()){
            if(p!=null){
                p.next = new ListNode(stack3.pop());
                p= p.next;
            }else{
                p =result;
                p.val=stack3.pop();
            }
        }
        return result;
    }
}


